//给定一个整数 n ，返回 n! 结果中尾随零的数量。 
//
// 提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：0
//解释：3! = 6 ，不含尾随 0
// 
//
// 示例 2： 
//
// 
//输入：n = 5
//输出：1
//解释：5! = 120 ，有一个尾随 0
// 
//
// 示例 3： 
//
// 
//输入：n = 0
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= n <= 104 
// 
//
// 
//
// 进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？ 
// Related Topics 数学 
// 👍 526 👎 0

package com.cute.leetcode.editor.cn;
public class FactorialTrailingZeroes {
    public static void main(String[] args) {
        new FactorialTrailingZeroes().new Solution().trailingZeroes(5);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 题目中最大的n给到了10000，再求阶乘的话可不是一个小数目（30000多位数）
     */
    class Solution {
        public int trailingZeroes1(int n) {
            if (n == 0) return 0;
            for (int i = n-1; i > 0 ; i--) {
                n *= i;
            }
            int count = 0;
            while ((n%10)==0){
                count++;
                n /= 10;
            }
            return count;

        }

        /**
         * 寻找因子对
         * 众所周知，只有2*5能凑出来10，多一个0，所以一个数的阶乘可以考虑从2-5因子对入手
         * 10 = 2*5  8 = 2*4  6 = 2*3  5 = 1*5  4 = 2*2  2 = 2*1
         * 可以发现5这个因子每5个数出现一次，2这个因子每2个数出现一次
         * 所以5一定可以匹配完，只需要统计5的个数即可
         * 只需要判断每个累乘的数有多少个 5 的因子即可。
         */
        public int trailingZeroes2(int n) {
            int count = 0;
            for (int i = 1; i <= n ; i++) {
                int N = i;
                while (N>0){//这里仅仅是统计了当前i中包含的5的个数
                    if (N%5==0){
                        count++;
                        N/=5;
                    }else break;
                }
            }
            return count;

        }

        /**
         * 为啥只需要统计n中5的个数呢？
         * 比如说n=8，那么n！=1*2*3*4*5*6*7*8，虽然这里面有好多个2（2、4、8、6）
         *      但是只有一个5可以和它配对
         * 再比如n=11，n！=1*2*3*4*5...*9*10*11,这里也只有2个5，所以说直接求n里面有几个5就可以了
         *
         * 理性分析，5这个因子每个5个数会出现一次，所以只需要用n/5就能算出来出现了多少个5
         * 但是每隔25个数会出现一次25，即两个5，所以还需要多统计一个5，即需要加上n/25
         * 同理还要加上n/125 ...
         * 最终5的个数就是 n/5 + n/25 + n/125 + ...
         *
         */
        public int trailingZeroes(int n) {
            int count = 0;
            while (n>0){
                //这里一开始计算是统计的5的个数
                // n/5之后下一轮是计算25的个数
                // 再下一轮是计算125的个数
                n/=5;
                count += n;

            }
            return count;

        }

    }

//leetcode submit region end(Prohibit modification and deletion)

}